import functools
class Solution(object):
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        @functools.cache
        def search(left, right):
            if right - left == 1:
                return left
            if right - left == 0:
                return 0
            min_val = float('inf')
            for k in range(left + 1, right):
                min_val = min(min_val, max(k + search(left, k - 1), k + search(k + 1, right)))
            return min_val

        return search(1, n)


data = Solution()
n = 200
print(data.getMoneyAmount(n))
